/*
 * @Author: kaikaima
 * @Date: 2021-01-11 18:58:40
 * @LastEditTime: 2021-01-12 22:07:22
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: /undefined/home/messi/Data_Structure_and_Algorithm_GIT/Group/main.h
 */

#include <iostream>
#include <vector>

#ifndef __hhxxttxs_GRAPH__
#define __hhxxttxs_GRAPH__

template <class Tnum, class Tvalue>
class Graph {
private:
    class path;
    class Node;
    class path{
        public:
            Tnum len;
            Node* beside;
            path* next;
            path() {beside=NULL;next=NULL;};
            path(Tnum _l, Node* _x) {len=_l;beside=_x;next=NULL;};
    };
    class Node{
            public:
                Tvalue name;
                path* first;
                Node() {first=NULL;};
                Node(Tvalue _n) {name=_n;first=NULL;};
    };
    typename std::vector<Node*> arr;
    void release (path* _x) {
                while(_x!=NULL){
                    path* x=_x;
                    _x=x->next;
                    delete x;}
                };
    Node* search(Tvalue _a) const;
public:
    Graph();
    Graph(Tvalue _a);
    Graph(Tvalue _a, Tvalue _b, Tnum _c);
    ~Graph();
    void insert(Tvalue _a, Tvalue _b, Tnum _c);
    Tnum how_long(Tvalue _a, Tvalue _b) const;
};

template <class Tnum, class Tvalue>
typename Graph<Tnum,Tvalue>::Node* Graph<Tnum,Tvalue>::search(Tvalue _a) const{
    Node* pp=arr[0];
    for(int i=0;i<arr.size();i++){
        pp=arr[i];
        if(pp->name==_a)
        return pp;
    }
    return NULL;
};

template <class Tnum, class Tvalue>
Graph<Tnum, Tvalue>::Graph(Tvalue _a){
    Node* a=new Node(_a);
    arr.push_back(a);
};

template <class Tnum, class Tvalue>
Graph<Tnum,Tvalue>::Graph(Tvalue _a, Tvalue _b, Tnum _c){
    Node* a=new Node(_a);
    Node* b=new Node(_b);
    a->first=new path(b, _c);
    b->first=new path(a, _c);
    arr.push_back(a);
    arr.push_back(b);
};

template <class Tnum, class Tvalue>
Graph<Tnum,Tvalue>::~Graph(){
    while(arr.begin()!=arr.end()){
        Node* ppp=*(arr.end()-1);
        release(ppp->first);
        delete ppp;
        arr.pop_back();
    }
};

template <class Tnum, class Tvalue>
void Graph<Tnum,Tvalue>::insert(Tvalue _a, Tvalue _b, Tnum _c){
    Node* ppp1=search(_a);
    Node* ppp2=search(_b);
    if(ppp1!=NULL && ppp2!=NULL){
        path* pp1=ppp1->first;
        while(pp1!=NULL) pp1=pp1->next;
        pp1=new path(_c,ppp2);
        path* pp2=ppp2->first;
        while(pp2!=NULL) pp2=pp2->next;
        pp2=new path(_c,ppp1);
    }
    else if(ppp1==NULL){
        if(ppp2==NULL){
            std::cout<<"error! Can't add an isolated node"<<std::endl;
            return;
        }
        path* pp=ppp2->first;
        ppp1=new Node(_a);
        while(pp!=NULL) pp=pp->next;
        pp=new path(_c,ppp1);
        ppp1->first=new path(_c,ppp2);
    }
    else
    {
        path* pp=ppp1->first;
        ppp2=new Node(_b);
        while(pp!=NULL) pp=pp->next;
        pp=new path(_c,ppp2);
        ppp2->first=new path(_c,ppp1);
    }    
};



template <class Tnum, class Tvalue>
Tnum Graph<Tnum, Tvalue>::how_long(Tvalue _a, Tvalue _b) const{
    Node* p1=search(_a);
    Node* p2=search(_b);
    if(p1==NULL || p2==NULL){
        std::cout<<"error! Can't find"<<_a<<std::endl;
        return -1;
    }
    
};
//*/
#else
//do nothing
#endif